package com.smh;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author shiminghui
 * @date 2025/2/8 16:18
 * @description: TODO
 */
public class _011_链表 {

    // 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode();
        ListNode cur = listNode;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return listNode.next;
    }

    // 使用递归实现
    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 != null ? list1 : list2;
        }
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists2(list1.next, list2); // 返回小的那个节点
            return list1;
        } else {
            list2.next = mergeTwoLists2(list1, list2.next);
            return list2;
        }
    }

    // 合并K个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;
        // 两个两个来合并
        for (int i = 1; i < length; i++) {
            lists[0] = mergeTwoLists(lists[0], lists[i]);
        }
        return lists[0];
    }

    // 通过获取最小值来合并
    // 获取每个链表的最小值，然后重新设置链表的头节点
    public ListNode mergeKLists2(ListNode[] lists) {
        ListNode listNode = new ListNode(-1);
        ListNode cur = listNode;
        while ((cur.next = getMinNode(lists)) != null) {
            cur = cur.next;
        }
        ;
        return listNode.next;
    }

    private ListNode getMinNode(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode minNode = null;
        int flag = 0;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                continue;
            }
            if (minNode == null || lists[i].val < minNode.val) {
                minNode = lists[i];
                flag = i;
            }
        }
        if (minNode != null) {
            lists[flag] = minNode.next;
        }
        return minNode;
    }

    // 两两合并链表，但是对链表进行操作，需要使用递归
    public ListNode split(ListNode[] lists, int i, int j) {
        if (i == j) {
            return lists[i];
        }
        int mid = (i + j) >>> 1;
        ListNode left = split(lists, i, mid);
        ListNode right = split(lists, mid + 1, j);
        return mergeTwoLists(left, right);
    }


    // 合并k个升序链表，用小顶堆
    public ListNode mergeKLists3(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(
                (o1, o2) -> {
                    return Integer.compare(o1.val, o2.val);
                }
        );
        ListNode res = new ListNode();
        ListNode curNode = res;
        for (ListNode list : lists) {
            if (list != null) {
                priorityQueue.offer(list);
            }
        }
        while (!priorityQueue.isEmpty()) {
            ListNode poll = priorityQueue.poll();
            if (poll.next != null) {
                priorityQueue.offer(poll.next);
            }
            curNode.next = poll;
            curNode = curNode.next;
        }
        return res.next;
    }

    // 链表中间值，快慢指针，若链表长度为偶数，则返回中间靠右那个节点
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    // 判断是否为回文链表
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        int[] index = {0};
        ListNode listNode = digui(head, list, index);
        if (listNode != null) {
            return true;
        }
        return false;
    }

    private ListNode digui(ListNode head, List<Integer> list, int[] index) {
        if (head == null) {
            return new ListNode();
        }
        list.add(head.val);
        ListNode listNode = digui(head.next, list, index);
        if (listNode == null) {
            return null;
        }
        if (list.get(index[0]++) == head.val) {
            return head;
        } else {
            return null;
        }
    }

    // 链表翻转解题
    public boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        if (head.next.next == null) {
            return head.val == head.next.val;
        }
        // 寻找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 将slow 节点作为翻转链表的头节点
        ListNode listNode = reverseList(slow);
        while (listNode != null && head != null) {
            if (head.val != listNode.val) {
                return false;
            }
            head = head.next;
            listNode = listNode.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        head.next = null; // 防止链表循环
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }


    public boolean isPalindrome3(ListNode head) {
        // 快慢指针
        ListNode slow = head;
        ListNode fast = head;
        ListNode newHead = null;
        ListNode oldHead = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 翻转链表
            ListNode tempNode = oldHead.next;
            oldHead.next = newHead;
            newHead = oldHead;
            oldHead = tempNode;

        }

        // 判断奇偶
        if (fast != null) {
            slow = slow.next;
        }

        // 判断链表是否为回文
        while (slow != null) {
            if (slow.val != newHead.val) {
                return false;
            }
            slow = slow.next;
            newHead = newHead.next;
        }
        return true;

    }

    // 判断是否有环
    public boolean hasCycle(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    // 链表环的入口节点
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }


    public class ListNode implements Comparable<ListNode> {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public int compareTo(ListNode o) {
            return Integer.compare(this.val, o.val);
        }
    }
}
